package top.minuy.algorithm.sort.quick;

import java.util.Random;
/**
 * 快速排序
 *
 * @author Minuy
 * @time 23:41
 * @date 2021/8/30
 */
public class QuickSort<E> {

    // static int depth = 0;
    // static int maxDepth = 0;

    private QuickSort() {
    }



    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 4);
    }

    public static <E extends Comparable<E>> void sort(E[] arr, int version) {
        Random random = new Random();
        if (version == 1) {
            sort_v1(arr, 0, arr.length, random);
        } else if (version == 2) {
            sort_v2(arr, 0, arr.length, random);
        } else if (version == 3) {
            sort_2w(arr, 0, arr.length, random);
        } else if (version == 4) {
            sort_3w(arr, 0, arr.length, random);
        }
        // System.out.println("MaxDepth = "+maxDepth);
    }

    //----------------------------------------333333333333333WWW------------------------------------

    // [l,r)
    private static <E extends Comparable<E>> void sort_3w(E[] arr, int l, int r, Random random) {
        // depth++;
        //  maxDepth = maxDepth>depth?maxDepth:depth;
        if (l >= r - 1) {
            //  depth--;
            return;
        }


        // [l,r)
        //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
        //该值介于[0,n)的区间
        int rd = random.nextInt(r - l) + l;
        // int rd = (r-l)/2 + l;
        swap(arr, l, rd);

        // [l+1,tl)<V
        // (tg,r-1]>V

        int tl = l + 1, tg = r - 1;

        for (int i = l + 1; i <= tg; ) {
            if (arr[l].compareTo(arr[i]) > 0) {
                swap(arr, tl, i);
                tl++;
                i++;
            } else if (arr[l].compareTo(arr[i]) < 0) {
                swap(arr, i, tg);
                tg--;
                // 这边来了个新元素，所以i不动
            } else {// arr[l] == arr[i]
                i++;
            }
        }

        swap(arr, l, tl - 1);
        //[l,tl-1) < V,(tg,r-1]>V

        tl--;
        //[l,tl) < V,(tg,r-1]>V

        tg++;
        //[l,tl) < V,[tg,r)>V
        //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

        // System.out.println("p = "+p);

        // 对上面的两个区间排序即可，中间相等的部分不予理会
        sort_3w(arr, l, tl, random);
        sort_3w(arr, tg, r, random);
        // depth--;
    }


//----------------------------------------2222222222222WWW------------------------------------

    // [l,r)
    private static <E extends Comparable<E>> void sort_2w(E[] arr, int l, int r, Random random) {
        // depth++;
        //  maxDepth = maxDepth>depth?maxDepth:depth;

        if (l >= r - 1) {
            //  depth--;
            return;
        }

        int p = partition_2w(arr, l, r, random);

        // System.out.println("p = "+p);

        sort_2w(arr, l, p, random);
        sort_2w(arr, p + 1, r, random);
        // depth--;
    }

    // [l,r)
    private static <E extends Comparable<E>> int partition_2w(E[] arr, int l, int r, Random random) {
        //该值介于[0,n)的区间
        int rd = random.nextInt(r - l) + l;
        // int rd = (r-l)/2 + l;
        swap(arr, l, rd);

        int i = l + 1, j = r - 1;
        // [l+1,i)<=V
        // (j,r-1]>=V
        while (true) {
            // System.out.println("i = " + i + " j = " + j);
            // out("当前数组", arr);

            // 每次改变i，j值时都要判断是不是可以结束循环了
            // 这里比较大小不能等于，等于的话若是全相同的数组直接到最后面去了，不符合分散原理
            while (j >= i && arr[l].compareTo(arr[i]) > 0/* l > i */) {  // 当i处的元素大于等于V时退出循环
                /**
                 * 一直向前寻找，直到小于等于V的值出现，停住
                 */
                i++;  // i往右移
                // System.out.println("i = "+i+" j = "+j);
            }

            // 每次改变i，j值时都要判断是不是可以结束循环了
            // 这里比较大小不能等于，等于的话若是全相同的数组直接到最前面去了，不符合分散原理
            while (j >= i && arr[l].compareTo(arr[j]) < 0/* l < j */) {
                /**
                 * 一直向后寻找，直到大于等于V的值出现，停住
                 */
                j--;  // j往左移
                // System.out.println("i = "+i+" j = "+j);
            }

            // 判断是否都遍历完了
            if (i >= j) break;

            // if(j>i) { // 正常交换

            // 交换完之后要移动一次，否则若两个位置刚好相等则会被这里卡住
            // 不加，下一次也是对当前位置判断，若这两个位置相等，则卡死
            // if(i!=j){
            swap(arr, i, j); // 等于的情况也交换，满足分散原理
            i++;
            j--;
            // }else if(arr[l].compareTo(arr[j]) < 0){
            //    j--;
            //    break;
            /// }
            // !!!!!!!!应该在偏移后判断是否要退出，直接写到while条件里就好了

            //}else {
            //    break; // i>=j时，就结束循环了
            //}
        }

        // 不要忘记处理相等的情况
        // 判断相等的这个元素是大于V的还是小于等于V的
        // if (i == j && arr[l].compareTo(arr[j]) < 0) {
        //     j--;
        // }

        swap(arr, l, j);

        return j;
    }

//----------------------------------------V2222222222222222------------------------------------

    // [l,r)
    private static <E extends Comparable<E>> void sort_v2(E[] arr, int l, int r, Random random) {
        // depth++;
        //  maxDepth = maxDepth>depth?maxDepth:depth;

        if (l >= r - 1) {
            //  depth--;
            return;
        }

        int p = partition_v2(arr, l, r, random);

        // System.out.println("p = "+p);

        sort_v2(arr, l, p, random);
        sort_v2(arr, p + 1, r, random);
        // depth--;
    }


    // [l,r)
    private static <E extends Comparable<E>> int partition_v2(E[] arr, int l, int r, Random random) {

        int rd = random.nextInt(r - l) + l;
        // int rd = (r-l)/2 + l;
        swap(arr, l, rd);

        // j：小于p点最后元素索引+1，[l+1,j) 是小于 p 点的元素
        // i：大于p点最后元素索引+1，[j,i) 是大于 p 点的元素
        int j = l + 1;
        for (int i = l + 1; i < r; i++) {
            if (arr[l].compareTo(arr[i]) > 0) {
                // 小于 隔断 的
                swap(arr, i, j);
                j++;
            }
            // 大于的不需要处理，等着被小的换掉
        }

        j--;
        // 这里变了，[l+1,j] 为小，[j+1,i) 为大
        swap(arr, l, j);
        // 这里把 隔断 放“中间”了，[l,j) 小，[j+1,i] 大
        // j 就是 隔断位置

        return j;
    }

//----------------------------------------V11111111111111------------------------------------

    private static <E extends Comparable<E>> void sort_v1(E[] arr, int l, int r, Random random) {
        // depth++;
        if (l >= r - 1) {
            // System.out.println("返回");
            // depth--;
            return;
        }
        int p = partition_v1(arr, l, r, random);

        // out("数组"+" "+depth,arr);

        // System.out.println("p = "+p);

        // System.out.println("L l = "+l+" r = "+p);
        sort_v1(arr, l, p, random);
        // System.out.println("R l = "+(p+1)+" r = "+r);
        sort_v1(arr, p + 1, r, random);
    }

    /**
     * 实现隔断，占用额外存储空间，从l到r，[l,r)
     *
     * @param arr 数组
     * @param l   左边索引，包括
     * @param r   右边索引，不包括
     * @param <E> 泛型支持
     * @return 隔断位置
     */
    private static <E extends Comparable<E>> int partition_v1(E[] arr, int l, int r, Random random) {
        int rd = random.nextInt(r - l) + l;
        // int rd = (r-l)/2 + l;
        swap(arr, l, rd);

        // 数组1
        Object[] temp1 = new Object[r - l];
        // 数组2
        Object[] temp2 = new Object[r - l];

        int size1 = 0, size2 = 0;

        E tempVal = arr[l];

        // 不需要处理第一个
        for (int i = l + 1; i < r; i++) {

            if (arr[i].compareTo(tempVal) <= 0) {
                // 比 隔断小
                temp1[size1] = arr[i];
                size1++;
            } else {
                temp2[size2] = arr[i];
                size2++;
            }
        }

        // 开始拼接数组
        int index = l;
        // 先把小的拼接上
        for (int i = 0; i < size1; i++) {
            arr[index] = (E) temp1[i];
            index++;
        }

        // 记录中间点的位置，等下返回
        int res = index;
        arr[index] = tempVal;
        index++;

        // 再拼接上大的
        for (int i = 0; i < size2; i++) {
            arr[index] = (E) temp2[i];
            index++;
        }

        // 这里返回的应该是小的长度加上
        // 返回拼接点位置
        return res;
    }

    //----------------------------------------To0000000000ol------------------------------------


    private static <E> void swap(E[] arr, int l, int r) {
        E temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    private static <E> void out(String str, Object[] arr) {
        System.out.println(str + " : ");
        for (Object i : arr) {
            if (i != null)
                System.out.print(i.toString() + " ");
        }
        System.out.println();
    }
}
